Stacks &
Queues
Stack ADT
definition:
A stack is a linear
sequence of data of the same type. It can be likened to a stack of plates
at a diner. The plates are taken off in a "last in, first out"
order.
operations of
a stack:
they have top and
bottom
can put on top and take off
top ONLY
key words to
remember:
push - to push is to place an item on the top
of a stack.
pop - to pop from a stack is to remove an
item from the top.
top - refers to the top of the
stack.
Pop does not return the value of the top of stack.
It just removes it.
Example of
Stack class:
class Stack
{
char ar[50]; // type of data in
stack
int
n; // number of elements
in stack
public:
Stack();
void push(char);
void pop();
char top()const;
bool empty()const;
bool full()const;
int
size()const;
};
/********************************/
Stack::Stack()
{
n=0; // says no elements
in array
}
/********************************/
bool Stack::empty()
{
return (n==0); // evaluates ==0 for true and != 0
for false
}
/********************************/
bool Stack::full()
{
return (n==50); // or use symbolic
constant
}
/********************************/
void Stack::push(char c)
{
if(n==50)
return;
// stack is full
// insert onto stack
ar[n] = c; // or optional ar[n++] =
c
n++;
}
/*********************************/
Stack::pop()
{
if (empty)
return;
n--;
}
Queue: (FIFO or first in first
out)
an abstract data type which is a sequence of data of the same
typeit has a front and a back.works well for list of things to do like print spoolersarray implementation is for
a set size of queue
linked list implementation
which are much more efficient
functions of a
queue:
push( ) to push a
value onto the queue.
pop( ) to pop a
value off of the queue.
front( ) similar
to top( ) in a stack so you can examine.
In an array
implementation of a queue you can push something onto the front of the list and
then push another element on. You can keep track of the list size.
Problem
with the array implementation is that you can keep track of size but when you
pull off the front, you have to move all other values down. This takes
time and resources.
Solution
is to keep track of the first and last numbers in the queue.
As you add in, the back moves. And as you pop things off, the front
moves as well. This is still a problem because you eventually run
out of room in the queue. Or… an even better solution to this problem is a
circular queue. This brings us to yet another new data
structure:
deque: (pronounced
deck)
a deque is a
linear data structure with a sequence of elements. It is a special case of
a queue has both a front and a back. It is essentially a double ended
queue. The main difference is that you can push and pop off of either the
front or back.