Contents |

A stack is a data structure in which the order
items are added to the structure affect the
order in which those items are removed.
In particular, a stack enforces *LIFO* ordering,
where *LIFO* stands for *Last-In-First-Out*.
For example, suppose the values 5, 13, and 7 were
added to a stack in the order given. Then the
first item removed from the stack would be 7,
the second 13, and the last 5.

Stacks can either be *bounded* or *unbounded*.
A bounded stack can only store a fixed number
of values while an unbounded stack can store
an unlimited number of values, conceptually speaking.

A bounded stack can used a least-recently-pushed replacement strategy when pushing a value onto a stack that is filled to capacity. That is, the least recently pushed value is replaced by the next-to-the-least recently pushed value, and so on.

The typical stack has one component, plus operations:

class stack { var store = ?; //operations ... }

The *store* can be set to a fillable, circular, or dynamic array
or a linked-list. If a fillable or circular array is used, a
capacity is typically given as an argument to the constructor;
this capacity is used to allocate the array.

The terms used in describing a stack are:

- push
- The name of the operation that adds a value to a stack.
- pop
- The name of the operation that removes a value from a stack.
Usually, the value removed is returned by the
*pop*operation. The*pop*operation returns the most recent value pushed that has not already been popped. - peek
- Like
*pop*, but the value is not removed from the stack. Consecutive peeks, with no intervening pushes or pops, always return the same value. Sometimes,*peek*is named*top*. - top of the stack
- The most recently pushed item that has not been popped.
- bottom of the stack
- The least recently pushed item that has not been popped.

A stack is a top-level data structure that is used in various algorithms.

Bounded stacks can be implemented with fillable arrays, while unbounded stacks can be implemented with dynamic arrays and singly linked-lists,

A bounded stack with a least-recently-pushed replacement strategy can be efficiently implemented with a circular array.

This operation adds a given *value* to the top of
the stack. If the stack is implemented with a fillable array
(dynamic or otherwise), the *push* operation translates to
the fillable array's *add-to-back* operation.
If the stack is implemented with a linked-list, the
push operation translates to the linked-list's *add-to-front* operation.

In the case of a
circular array-based bounded stack with a least-recently-pushed replacement
strategy, the *push*
operation translates to the array's *add-to-back*
operation. However, the *add-to-back* operation should
not signal an error if the array is full but should
instead overwrite the value at the start index as
well as incrementing the start index. This can
be accomplished with a *add-to-back* operation
followed by a *remove-from-front* operation.

Pushing a value onto a stack is expected to take *Θ(1)* time.

This operation removes (and returns) the *value* at the top of
the stack. If the stack is implemented with a fillable array
(dynamic or otherwise), the *pop* operation translates to
the array's *remove* operation.
If the stack is implemented with a linked-list, the
*pop* operation translates to the linked-list's
*remove-from-front* operation.

Popping a value from a stack is expected to take *Θ(1)* time.

The *peek* operation
can be implemented solely using *pop* and *push*:

function peek() { var value; value = pop(); push(value); return value; }

but this is not considered a good idea since it inflates
the number of pushes and pops a stack handles over the course
of its lifetime. Typically, for stacks implemented with
fillable arrays, the peek operation translates to the
array's *get* operation using an index of *size* - 1.
For stacks implemented with linked-lists, the peek operation
translates to the list's *get* operation using an index of zero.

This operation returns true if all pushed values have been popped, false otherwise. This can be done simply by incrementing a counter (initialized to zero) every time a push is performed and decrementing the counter every time a pop is performed. At points in time when the counter is zero, the stack is empty.

It would be an error, of course, if the counter was ever less than zero, indicating there were more pops than pushes.

The *is-empty* operation is expected to take *Θ(1)* time.

This operation returns true if the store is full, but only needs to be implemented for bounded stacks without a replacement policy.

- These values are pushed onto a stack in the order given: 3, 8, 1. A pop operation would return which value?
- 1
- 3
- 8
- 3 and 1
- 3 and 8

- Consider a stack based upon a fillable array with pushes onto the back of the array. What is the best one can do in terms of worst case behavior for
*push*and*pop*, respectively? You may assume there is sufficient space for each operation.- constant and constant
- constant and linear
- linear and linear
- linear and constant

- Consider a stack based upon a circular array with pushes onto the back of the array. What is the best one can do in terms of worst case behavior for
*push*and*pop*, respectively? You may assume there is sufficient space for each operation.- constant and constant
- constant and linear
- linear and linear
- linear and constant

- Consider a stack based upon a dynamic array with pushes onto the back of the array. What is the best one can do in terms of worst case behavior for
*push*and*pop*, respectively? You may assume the array does shrink.- constant and constant
- constant and linear
- linear and linear
- linear and constant

- Consider a stack based upon a dynamic circular array with pushes onto the front of the array. What is the best one can do in terms of worst case behavior for
*push*and*pop*, respectively? You may assume the array does not shrink.- constant and constant
- constant and linear
- linear and linear
- linear and constant

- Consider a stack based upon a singly-linked list without a tail pointer with pushes onto the front of the list. What is the best one can do in terms of worst case behavior for
*push*and*pop*, respectively?- constant and constant
- constant and linear
- linear and linear
- linear and constant

- Consider a stack based upon a singly-linked list with a tail pointer with pushes onto the back of the list. What is the best one can do in terms of worst case behavior for
*push*and*pop*, respectively?- constant and constant
- constant and linear
- linear and linear
- linear and constant

- Consider a stack based upon a doubly-linked list with a tail pointer with pushes onto the back of the list. What is the best one can do in terms of worst case behavior for
*push*and*pop*, respectively?- constant and constant
- constant and linear
- linear and linear
- linear and constant

Contents |