• Choose a category
• All
• Classic-Fiction

Complexity

O (1)

Name

stack_size

Synopsis

int stack_size(const Stack *stack);

Return Value

Number of elements in the stack.

Description

Macro that evaluates to the number of elements in the stack specified by stack.

Complexity

O (1)

Implementation and Analysis of Stacks

The structure Stack is the stack data structure . One way to implement a stack is as a linked list. A simple way to do this is to typedef Stack to List (see Example 6.1). In addition to simplicity, using a typedef has the benefit of making the stack somewhat polymorphic. Informally, polymorphism is a principle normally associated with object-oriented languages that allows an object (a variable) of one type to be used in place of another. This means that because the stack is a linked list, and hence has the same properties as a linked list, we can use linked list operations on it in addition to those of a stack. Thus, the stack can behave like a linked list when we want it to.

As an example, suppose we want to traverse the elements of a stack, perhaps so we can display them or determine whether a specific element resides in the stack. To do this, we get the element at the head of the list using list_head and traverse the list using list_next. Using only stack operations, we would have to pop the elements one at a time, inspect them, and push them onto another stack temporarily. Then, after accessing all of the elements, we would need to rebuild the original stack by popping the elements off the temporary stack and pushing them back onto the original one. This method would be less efficient and undoubtedly would look less than intuitive in a program.

Example 6.1. Header for the Stack Abstract Datatype

/*****************************************************************************

* *

* ------------------------------- stack.h -------------------------------- *

* *

*****************************************************************************/

#ifndef STACK_H

#define STACK_H

#include

#include "list.h"

/*****************************************************************************

* *

* Implement stacks as linked lists. *

* *

*****************************************************************************/

typedef List Stack;

/*****************************************************************************

* *

* --------------------------- Public Interface --------------------------- *

* *

*****************************************************************************/

#define stack_init list_init

#define stack_destroy list_destroy

int stack_push(Stack *stack, const void *data);

int stack_pop(Stack *stack, void **data);

#define stack_peek(stack) ((stack)->head == NULL ? NULL : (stack)->head->data)

#define stack_size list_size

#endif

stack_init

The stack_init operation initializes a stack so that it can be used in other operations (see Example 6.1). Since a stack is a linked list and requires the same initialization, stack_init is defined to list_init.

The runtime complexity of stack_init is the same as list_init, or O (1).

stack_destroy

The stack_destroy operation destroys a stack (see Example 6.1). Since a stack is a linked list and requires being destroyed in the same manner, stack_destroy is defined to list_destroy.

The runtime complexity of stack_destroy is the same as list_destroy, or O (n), where n is the number of elements in the stack.

stack_ push

The stack_ push operation pushes an element onto the top of a stack by calling list_ins_next to insert an element pointing to data at the head of the list (see Example 6.2).

The runtime complexity of stack_ push is the same as list_ins_next, or O (1).

stack_ pop

The stack_ pop operation pops an element off the top of a stack by calling list_rem_next to remove the element at the head of the list (see Example 6.2). The list_rem_next operation sets data to point to the data from the element removed.

The runtime complexity of stack_ pop is the same as list_rem_next,