PROJECT: DOUBLY LINKED STACKS (dls0)

OBJECTIVE

Building on top of your doubly-linked list implementation, implement a stack.

TASK

By the deadline, please do the following:

  • create a Stack management struct, containing a size element, and a top Node pointer
    • size, if 0, will indicate an unbounded stack (positive means bounded)
    • top points to the node at the top of the stack (on the list)
  • implement an mkstack() function
  • implement an rmstack() function
  • implement a push() function
  • implement a pop() function
  • implement a peek() function
  • implement an isempty() function

BACKGROUND

A stack is a LIFO (Last-In, First-Out) data structure, which we will simplify by building on top of our existing doubly-linked list infrastructure.

The last item placed on the top of the stack will be the first item retrieved from the stack.

The strength of the stack comes from the particular restrictions we place on its access: we can only access the top of the stack. This will be either the start or end of your underlying list (your implementation, you pick which and run with it).

The stack push() function will take the node and place it on the top of the stack (by calling the appropriate underlying list function)

The stack pop() function will retrieve the node at the top of the stack (in the process adjusting top to point to the new node at the top of the stack)

You will want to call upon the underlying list functionality to do the heavy-lifting.

For the stack, PUSH and POP are the two central actions. Without them there is no stack.

Often, you will find stacks also implement other helper functions, such as an isempty() function which returns a boolean value regarding the stack status- true for an empty stack, false for a populated one.

Then there's peek(), which is like a non-destructive pop(): it retrieves a copy of the node at the top of the stack, making no actual changes to the stack itself.

SUBMISSION

156:dls0:final tally of results (156/156)
*:dls0:create stack struct [13/13]
*:dls0:create and test mkstack function [26/26]
*:dls0:create and test rmstack function [13/13]
*:dls0:create and test push function [26/26]
*:dls0:adapt and test pop function [26/26]
*:dls0:adapt and test isempty function [26/26]
*:dls0:adapt and test peek function [26/26]

Additionally:

  • Solutions not abiding by spirit of project will be subject to a 25% overall deduction
  • Solutions not utilizing descriptive why and how comments will be subject to a 25% overall deduction
  • Solutions not utilizing indentation to promote scope and clarity will be subject to a 25% overall deduction
  • Solutions not organized and easy to read (assume a terminal at least 90 characters wide, 40 characters tall) are subject to a 25% overall deduction