Lab46 Wiki

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
======Project: Stack Library Implementation======

A project for Data Structures by Brad Hammond during the Fall of 2011.


=====Objectives=====
Implement a doubly linked list as a stack library to better understand stacks in memory.

=====Prerequisites=====
In order to successfully accomplish/perform this project, the listed resources/experiences need to be consulted/achieved:

  * understand pointers
  * understand structs
  * understand malloc()
  * understand LIFO
  * ability to create a linked data structure

=====Background=====
The idea behind this project is to create a stack and implement it in a library to give a better understanding of how stacks exist in computer memory.
A stack is an abstract data structure that can be based on either a linked list or an array. It has three basic operations that can be performed on it: push, pop, and peek. Push adds a value to the base of the stack and pushes all other values up one position on the stack. Pop will remove the value at the base of the stack and then move all other values down by one position. Peek allows one to look at the value at the base of the stack without actually removing it.

=====Attributes=====

  * pointers: pointers are at the heart of dynamic structures.
  * malloc/new: dynamic memory allocation.
  * linked lists: this code is going to implement linked lists.
  * doubly linked lists: not only is the code implementing a linked list, it is implementing doubly linked lists.
  * libraries: this code will be part of a library that can be reused in other projects

=====Code=====

<code c>
#include "List.h"

#define NULL 0

int empty(List *s)
{
	if (listLength(s) == 0)
		return 1;
	else
		return 0;
}

int peek(List *s)
{
	int topVal;

	if (s -> first == NULL)
		return -1;

	topVal = getValue(s, 0);
	return topVal;
}

int push(List *s, int val)
{
	if (s -> first == NULL)
		appendToList(s, val);
	else
		insertInList(s, 0, val);
	return 0;
}

int pop(List *s)
{
	int value;

	if (s -> first == NULL)
		return -123456789;
	value = getValue(s, 0);
	deleteNode(s, 0);

	return value;
}
</code>
<code c>
#ifndef _STACK
#define _STACK

//Tests if the stack is empty. If the stack is empty
//1 is returned or a 0 if the stack is not empty. If
//the stack does not exist a -1 will be returned.
int empty(List *s);

//Looks at the value at the stop of the stack without
//removing it and returns that value upon success. If
//an error occurs a -1 is returned. Accepts a stack
//pointer as a parameter.
int peek(List *s);

//Pushes a value onto the stack. Returns a 0 upon success
//and a -1 if an error occurs. Its paramaters are a 
//stack pointer and an integer value.
int push(List *s, int val);


//Returns the value from the top of the stack and then 
//removes it from the stack. Upon success the value
//at the top of the stack is returned. If an error
//occurs a large negative int is returned.
int pop(List *s);

//Searches through the stack to find a given value. If
//the value is found, the position of the value is returned.
//If an error occurs, -1 is returned.
//int search(List *s, int);

#endif
</code>
=====Execution=====
Again, if there is associated code with the project, and you haven't already indicated how to run it, provide a sample run of your code:

<cli>
brad@dhcp-181:/media/06F6-9DC2/Notepad++/Programs/LinkedList$ gcc -o lStack LinkedList.c Stack.c lStack.c
brad@dhcp-181:/media/06F6-9DC2/Notepad++/Programs/LinkedList$ ./lStack
0 100 200 300 400 500 600 700 800 900 1000 1100 1200 1300 1400 1500 1600 1700 1800 1900 2000 2100 2200 2300 2400 2500 2600 2700 2800 2900 3000 3100 3200 3300 3400 3500 3600 3700 3800 3900 4000 4100 4200 4300 4400 4500 4600 4700 4800 4900 5000 5100 5200 5300 5400 5500 5600 5700 5800 5900 6000 6100 6200 6300 6400 6500 6600 6700 6800 6900 7000 7100 7200 7300 7400 7500 7600 7700 7800 7900 8000 8100 8200 8300 8400 8500 8600 8700 8800 8900 9000 9100 9200 9300 9400 9500 9600 9700 9800 9900 
9900 9800 9700 9600 9500 9400 9300 9200 9100 9000 8900 8800 8700 8600 8500 8400 8300 8200 8100 8000 7900 7800 7700 7600 7500 7400 7300 7200 7100 7000 6900 6800 6700 6600 6500 6400 6300 6200 6100 6000 5900 5800 5700 5600 5500 5400 5300 5200 5100 5000 4900 4800 4700 4600 4500 4400 4300 4200 4100 4000 3900 3800 3700 3600 3500 3400 3300 3200 3100 3000 2900 2800 2700 2600 2500 2400 2300 2200 2100 2000 1900 1800 1700 1600 1500 1400 1300 1200 1100 1000 900 800 700 600 500 400 300 200 100 0 
brad@dhcp-181:/media/06F6-9DC2/Notepad++/Programs/LinkedList$ 

</cli>

=====Reflection=====
Comments/thoughts generated through performing the project, observations made, analysis rendered, conclusions wrought. What did you learn from doing this project?

Writing the stack wasn't a huge feat. I'd say 75% of the work was done in the linked list library. It was a matter of implementing the pop, push, and peek functions. I've added another function to the stack library which tests whether or not the stack is empty. And on a side not. For some reason that I am not quite aware when I compiled this program NULL was not being recognized so I defined it in the header file.
=====References=====
In performing this project, the following resources were referenced:

  * [[http://lab46.corning-cc.edu/opus/fall2011/bh011695/start#stacks_array-based_linked-list_based]]
  * [[http://lab46.corning-cc.edu/user/bh011695/portfolio/libdll]]
  * [[http://en.wikipedia.org/wiki/Stack_data_structure]]

Generally, state where you got informative and useful information to help you accomplish this project when you originally worked on it (from Google, other wiki documents on the Lab46 wiki, etc.)
Lab46 Wiki

User Tools

Site Tools

Page Tools
