Doubly Linked-Lists Top Queues Contents

Stacks

Synopsis

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.

Structure

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.

Vocabulary

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.

Supports

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

Dependencies

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.

Operations

push

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.

pop

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.

peek

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.

is-empty

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.

is-full

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

Concept Inventory

     
  1. These values are pushed onto a stack in the order given: 3, 8, 1. A pop operation would return which value?
    1. 1
    2. 3
    3. 8
    4. 3 and 1
    5. 3 and 8
     
  2. 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.
    1. constant and constant
    2. constant and linear
    3. linear and linear
    4. linear and constant
     
  3. 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.
    1. constant and constant
    2. constant and linear
    3. linear and linear
    4. linear and constant
     
  4. 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.
    1. constant and constant
    2. constant and linear
    3. linear and linear
    4. linear and constant
     
  5. 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.
    1. constant and constant
    2. constant and linear
    3. linear and linear
    4. linear and constant
     
  6. 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?
    1. constant and constant
    2. constant and linear
    3. linear and linear
    4. linear and constant
     
  7. 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?
    1. constant and constant
    2. constant and linear
    3. linear and linear
    4. linear and constant
     
  8. 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?
    1. constant and constant
    2. constant and linear
    3. linear and linear
    4. linear and constant

lusth@cs.ua.edu


Doubly Linked-Lists Top Queues Contents